1. Field of the Invention
This invention relates to digital signal processing.
2. Background Information
Digital signal processing techniques may be used to process signals at baseband, intermediate, and radio frequencies. In addition to their use in new applications, such techniques are also replacing analog processing techniques in existing applications such as signal filtering. The numerous advantages that a digital filter may possess over an analog counterpart include a lack of impedance matching problems, guaranteed stability and/or phase linearity, freedom from a change in response due to aging, and programmability and ease of alteration.
Digital filter s are implemented primarily as linear constant coefficient filters. Such filters may be broadly divided into two lasses: infinite-impulse-response (IIR) filters and finite impulse response (FIR) filters. By incorporating feedback, IIR filters require fewer taps to achieve the same performance. Such filters cause less delay and can be implemented with less hardware than FIR filters with similar characteristics. However, IIR filters are harder to design than FIR filters, generally have nonlinear phase characteristics, and may have stability problems as well.
In contrast to IIR filters, FIR filters are guaranteed to produce abounded output in response to a bounded input. Moreover, if the coefficients of a FIR filter are symmetric (or antisymmetric), then the filter will have a linear phase response. One basic FIR filter system is illustrated in FIG. 1. Shift register 20 receives an input signal (e.g. a series of digital values) and outputs an N-element input vector S10 to filter 40. In this example, a new input value is shifted into register 20 upon a predetermined transition of a clock signal from clock 30. Filter 40 contains a filter coefficient vector of length N, N multipliers, and an N-input adder. For each instance of input vector S10 (expressed as a series of values X0, X1, X2, . . . , XN), filter 40 outputs a value y according to the expression   y  =            ∑              n        =        0                    N        -        1              ⁢          xe2x80x83        ⁢                  x        n            ⁢                        h          n                .            
Further information on the theory and design of digital filters may be found in such documents as Electronic Filter Design Handbook, 2nd ed., by A. B. Williams and F. J. Taylor, McGraw-Hill, New York, 1988; Digital Filtering: an introduction, E. P. Cunningham, Houghton Mifflin, Boston, 1992; and section XVI of The Circuits and Filters Handbook, ed. by W.-K. Chen, CRC Press, Boca Raton, Fla., 1995.
Lookup tables (LUTs) are used in various computing contexts to hold decision information that cannot easily be expressed mathematically. Two examples of information that may be stored in a LUT are (1) the mapping of IP addresses to aliases or to physical network locations, and (2) colormaps. Lookup tables have also been used in waveform generation applications to hold values that are frequently used but may be cumbersome to calculate, such as a mapping from a time index (x) into a trigonometric value (such as sin x or cos x).
A digital filter as shown in FIG. 1 is a calculation-intensive circuit. Because the set of possible input values to a digital filter is finite, the response of such a filter is completely deterministic and may be specified before runtime. However, it has not generally been feasible to use LUTs in digital filtering applications. In order to directly represent every possible output of an N-tap FIR filter which receives an input data stream M bits wide, a lookup table of size 2Mxc3x97N would be required. For an 8-bit-wide input and a relatively short 16-tap filter, such a table would have to contain 2128 (or on the order of 1038) symbol storage spaces.
If the input data stream for the filter is only 1 bit wide (i.e. binary-valued), then the size of the lookup table reduces to 2N symbol storage spaces. Even in this case, however, the size of the filter is severely limited by the resulting storage requirements: for example, a 16-tap filter would require 216 symbol storage spaces (i.e. one megabit of storage area for every bit of the width of the output symbols). Where the performance of a longer filter is required or the application imposes severe circuit area and/or power constraints (e.g. as in a portable device for wireless communications), FIR implementation using lookup tables may not be feasible.
A system for digital filtering according to one embodiment of the invention includes a digital filter that has a set of logic gates, a state storage, and a multiplexer. The set of logic gates is configured and arranged to receive an input vector and a phase count signal. The phase count signal may count at a rate that is a multiple of the rate of a clock associated with the input vector. The set of logic gates is configured and arranged to produce a state select vector based on at least a portion of the phase count signal and at least a portion of the input vector. For example, the set of logic gates may map the input vector to the state select vector according to a sequence select signal based on at least a portion of the phase count signal.
The state storage has two or more storage banks, each configured and arranged to receive the state select vector and to produce a state signal indicated by that vector. For example, the state storage (or each of the storage banks) may include one or more lookup tables having values based on components of a finite-impulse-response filter coefficient vector (such as a symmetric or antisymmetric filter coefficient vector). The state storage may also include combinatorial logic configured and arranged to produce a signal (such as a zero select signal) based on at least part of the state select vector.
The multiplexer is configured and arranged to receive the two or more state signals and to pass a selected state signal corresponding to a bank select signal. The bank select signal is based on the phase count signal and may also be based on at least a part of the input vector.
The digital filter may also include an inverter configured and arranged to produce an output signal based on the selected state signal and an invert signal. The invert signal is based on at least part of the input vector and may also be based on the phase count signal. Additionally, components of at least a portion of the state select vector may be based on the invert signal.
Such a system may include a shift register configured and arranged to produce the input vector and a phase counter configured and arranged to produce the phase count signal. The system may also include additional digital filters, with one or more adders configured and arranged to produce a sum based on the selected state signals.
A method of digital filtering according to an embodiment of the invention includes receiving an input vector and a phase count signal and mapping the input vector to a state select vector according to the phase count signal. The method also includes inputting the state select vector to a state storage that includes two or more storage banks. From each of the storage banks, a state signal corresponding to the state select vector is received, and one from among the state signals is selected according to a bank select signal. As noted above, the bank select signal is based on the phase count signal and may also be based on at least a part of the input vector.
Additional embodiments of the invention and applications thereof are described and/or illustrated herein. For example, a system or method according to an embodiment of the invention may be applied to filter a binary data stream according to the 48-tap FIR filter shown in TABLE 1.